<!DOCTYPE html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head>
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.3" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/avatar.jpg?v=5.1.3">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/avatar.jpg?v=5.1.3">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/avatar.jpg?v=5.1.3">


  <link rel="mask-icon" href="/images/avatar.jpg?v=5.1.3" color="#222">





  <meta name="keywords" content="算法,Algorithms Notes," />










<meta name="description" content="观察运行时间和输入本身相对无关，主要取决于问题规模例：统计文件中三个数和为0的数量 12345678910111213public class ThreeSum&amp;#123;    public static int count(int a[])&amp;#123;        int N = a.length, cnt = 0;        for(int i = 0; i &amp;lt; N; i++)&amp;">
<meta name="keywords" content="算法,Algorithms Notes">
<meta property="og:type" content="article">
<meta property="og:title" content="（二）基础（Fundamentals）：算法分析">
<meta property="og:url" content="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/index.html">
<meta property="og:site_name" content="Fighter&#39;s Blog">
<meta property="og:description" content="观察运行时间和输入本身相对无关，主要取决于问题规模例：统计文件中三个数和为0的数量 12345678910111213public class ThreeSum&amp;#123;    public static int count(int a[])&amp;#123;        int N = a.length, cnt = 0;        for(int i = 0; i &amp;lt; N; i++)&amp;">
<meta property="og:locale" content="zh-Hans">
<meta property="og:image" content="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/典型对象的内存需求.png">
<meta property="og:image" content="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/数组对内存的典型需求.png">
<meta property="og:image" content="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/字符串的内存需求.png">
<meta property="og:image" content="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/quick-union算法概述.png">
<meta property="og:image" content="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/quick-union最坏情况.png">
<meta property="og:image" content="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/各种union-find算法性能特点.png">
<meta property="og:updated_time" content="2018-02-05T05:27:46.805Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="（二）基础（Fundamentals）：算法分析">
<meta name="twitter:description" content="观察运行时间和输入本身相对无关，主要取决于问题规模例：统计文件中三个数和为0的数量 12345678910111213public class ThreeSum&amp;#123;    public static int count(int a[])&amp;#123;        int N = a.length, cnt = 0;        for(int i = 0; i &amp;lt; N; i++)&amp;">
<meta name="twitter:image" content="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/典型对象的内存需求.png">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.3',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/"/>





  <title>（二）基础（Fundamentals）：算法分析 | Fighter's Blog</title><!-- hexo-inject:begin --><!-- hexo-inject:end -->
  








</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <!-- hexo-inject:begin --><!-- hexo-inject:end --><div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Fighter's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle">深度沉迷学习</p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="Fighter.">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Fighter's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">（二）基础（Fundamentals）：算法分析</h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-12-30T23:59:11+08:00">
                2017-12-30
              </time>
            

            

            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/算法与数据结构/" itemprop="url" rel="index">
                    <span itemprop="name">算法与数据结构</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          
            <span class="post-meta-divider">|</span>
            <span class="page-pv"><i class="fa fa-file-o"></i>
            <span class="busuanzi-value" id="busuanzi_value_page_pv" ></span>
            </span>
          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <h2 id="观察"><a href="#观察" class="headerlink" title="观察"></a>观察</h2><p>运行时间和输入本身相对无关，主要取决于问题规模<br>例：统计文件中三个数和为0的数量</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ThreeSum</span></span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">(<span class="keyword">int</span> a[])</span></span>&#123;</div><div class="line">        <span class="keyword">int</span> N = a.length, cnt = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++)&#123;</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j = i + <span class="number">1</span>; j &lt; N; j++)&#123;</div><div class="line">                <span class="keyword">for</span> (<span class="keyword">int</span> k = j + <span class="number">1</span>; k  &lt; N; k++)&#123;</div><div class="line">                    <span class="keyword">if</span>(a[i] + a[j] + a[k] == <span class="number">0</span>)</div><div class="line">                        cnt += <span class="number">1</span>;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>一种表示计时器的抽象数据类型：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">StopWatch</span></span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">long</span> start;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">StopWatch</span><span class="params">()</span></span>&#123;</div><div class="line">        start = System.currentTimeMillis();</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">double</span> <span class="title">elapsedTime</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">long</span> now = System.currentTimeMillis();</div><div class="line">        <span class="keyword">return</span> (now - start) / <span class="number">1000.0</span>;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<a id="more"></a>
<h2 id="数学模型"><a href="#数学模型" class="headerlink" title="数学模型"></a>数学模型</h2><p>程序运行总时间主要和两点有关：</p>
<ul>
<li>执行每条语句的耗时（取决于计算机、Java编译器和操作系统）</li>
<li>执行每条语句的频率（取决于程序本身和输入）</li>
</ul>
<p>对于执行频率，有些分析很容易，如在 Three.count() 中将 cnt 设为 0 的语句只会执行一次；有些需要深入分析，如 Three.count() 中的 if 语句会执行 $\frac{N(N-1)(N-2)}{6}$ 次。</p>
<h3 id="近似"><a href="#近似" class="headerlink" title="近似"></a>近似</h3><blockquote>
<p>用 ~f(N) 表示所有随着N增大除以f(N)的结果趋近于1的函数。用g(N)~f(N)表示随着g(N)/f(N) 随着N增大趋近于1。</p>
</blockquote>
<p>一般用到的近似方式都是 $g(N)\sim f(N)$，其中 $f(N)=N^b(logN)^c$，其中a,b和c均为常数，将f(N)称为g(N)的增长数量级。<br>常见的增长数量级函数:</p>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">描述</th>
<th style="text-align:center">函数 B</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center"> 常数级</td>
<td style="text-align:center">1</td>
</tr>
<tr>
<td style="text-align:center"> 对数级</td>
<td style="text-align:center">$logN$</td>
</tr>
<tr>
<td style="text-align:center"> 线性级</td>
<td style="text-align:center">$N$</td>
</tr>
<tr>
<td style="text-align:center"> 线性对数级</td>
<td style="text-align:center">$NlogN$</td>
</tr>
<tr>
<td style="text-align:center"> 平方级</td>
<td style="text-align:center">$N^2$</td>
</tr>
<tr>
<td style="text-align:center"> 立方级</td>
<td style="text-align:center">$N^3$</td>
</tr>
<tr>
<td style="text-align:center"> 指数级</td>
<td style="text-align:center">$2^N$</td>
</tr>
</tbody>
</table>
</div>
<blockquote>
<p>执行最频繁的执行决定了程序执行的总时间——称这些指令为程序的<em>内循环</em></p>
</blockquote>
<h3 id="成本模型"><a href="#成本模型" class="headerlink" title="成本模型"></a>成本模型</h3><p>用<strong>成本模型</strong>来评估算法的性质，这个模型定义了所研究算法中的基本操作。例如，3-Sum问题的成本模型是访问数组元素的次数。</p>
<h3 id="构建运行时间的数学模型所需步骤："><a href="#构建运行时间的数学模型所需步骤：" class="headerlink" title="构建运行时间的数学模型所需步骤："></a>构建运行时间的数学模型所需步骤：</h3><ol>
<li>确定<strong>输入模型</strong>，定义问题规模</li>
<li>识别<strong>内循环</strong></li>
<li>根据内循环中的操作确定<strong>成本模型</strong></li>
<li>对给定输入，判断这些操作的执行频率</li>
</ol>
<p>如二分查找，它的输入模型是大小为N的数组a[]，内循环是while循环中所有语句，成本模型是比较操作（比较两个数组元素的值）</p>
<h2 id="设计更快的算法"><a href="#设计更快的算法" class="headerlink" title="设计更快的算法"></a>设计更快的算法</h2><h3 id="2-Sum-问题"><a href="#2-Sum-问题" class="headerlink" title="2-Sum 问题"></a>2-Sum 问题</h3><p>假设所有整数各不相同，这个问题很容易在平方级别——双重循环来解决，下面利用归并排序和二分查找在线性对数级别解决 2-Sum 问题：</p>
<blockquote>
<p>思路：当且仅当 <code>-a[i]</code> 存在于数组中（且<code>a[i]</code>非0）时，<code>a[i]</code> 存在于某个和为0的整数对中。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">TwoSumFast</span></span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">(<span class="keyword">int</span>[] a)</span></span>&#123;</div><div class="line">        <span class="comment">//先排序</span></div><div class="line">        Arrays.sort(a);</div><div class="line">        <span class="keyword">int</span> cnt = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; a.length; i++)&#123;</div><div class="line">            <span class="keyword">if</span>(BinarySearch.rank(-a[i], a) &gt; i)</div><div class="line">                cnt++;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> cnt;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>归并排序所需时间与 NlogN 成正比，二分查找所需时间和 logN 成正比，因此整个算法运行时间和 NlogN 成正比。</p>
<h3 id="3-Sum-问题"><a href="#3-Sum-问题" class="headerlink" title="3-Sum 问题"></a>3-Sum 问题</h3><p>同样假设所有整数各不相同，同上面一样，当且仅当 <code>-(a[i] + a[j])</code> 在数组中（不是 <code>a[i]</code> 也不是 <code>a[j]</code>）时，整数对（<code>a[i]</code> 和 <code>a[j]</code>）为某个和为0的三元组的一部分。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ThreeSumFast</span></span>&#123;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">(<span class="keyword">int</span>[] a)</span></span>&#123;</div><div class="line">        <span class="comment">//先排序</span></div><div class="line">        Arrays.sort(a);</div><div class="line">        <span class="keyword">int</span> cnt = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; a.length; i++)&#123;</div><div class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> j = i + <span class="number">1</span>; j &lt; a.length; j++)</div><div class="line">                <span class="keyword">if</span>(BinarySearch.rank(-(a[i] + a[j]), a) &gt; j)</div><div class="line">                    cnt++;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> cnt;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h2 id="内存"><a href="#内存" class="headerlink" title="内存"></a>内存</h2><h3 id="对象"><a href="#对象" class="headerlink" title="对象"></a>对象</h3><img src="/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/典型对象的内存需求.png" title="典型对象的内存需求">
<h3 id="数组"><a href="#数组" class="headerlink" title="数组"></a>数组</h3><img src="/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/数组对内存的典型需求.png" title="数组对内存的典型需求">
<h3 id="字符串对象"><a href="#字符串对象" class="headerlink" title="字符串对象"></a>字符串对象</h3><img src="/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/字符串的内存需求.png" title="字符串的内存需求">
<p>当调用 <code>substring()</code> 方法时，就创建了一个新的 <code>String</code> 对象（40字节），但仍然重用了相同的 <code>value[]</code> 数组，因此该字符串的子字符串只会使用40字节的内存，也就是说，一个子字符串的额外内存是一个常数，构造一个子字符串所需时间也是常数。</p>
<h2 id="举例：union-find-算法"><a href="#举例：union-find-算法" class="headerlink" title="举例：union-find 算法"></a>举例：union-find 算法</h2><h3 id="动态连通性"><a href="#动态连通性" class="headerlink" title="动态连通性"></a>动态连通性</h3><p>问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数p q可以被理解为“p和q是相连的”，具有如下性质；</p>
<ul>
<li>自反性：p 和 p 是</li>
<li>对称性：若 p 和 q 相连，则 q 和 p 也相连</li>
<li>传递性：若 p 和 q 相连且 q 和 r 相连，则 p 和 r 也相连</li>
</ul>
<p><strong>union-find 算法API</strong></p>
<div class="table-container">
<table>
<thead>
<tr>
<th>方法名</th>
<th>操作</th>
</tr>
</thead>
<tbody>
<tr>
<td>UF(int N)</td>
<td>以整数标识（0 到 N-1）初始化N个触点</td>
</tr>
<tr>
<td>void union(int p, int q)</td>
<td>在 p 和 q 之间添加一条连接 </td>
</tr>
<tr>
<td>int find(int p)</td>
<td>p 所在的分量的标识符（0 到 N-1）</td>
</tr>
<tr>
<td>boolean connected(int p, int q)</td>
<td>如果 p 和 q 存在于同一个分量则返回 true</td>
</tr>
<tr>
<td>int count()</td>
<td>连通分量的数量</td>
</tr>
</tbody>
</table>
</div>
<blockquote>
<p>用一个<strong>以触点为索引</strong>的数组 <code>id[]</code> 作为基本数据结构来表示所有分量。初始有 N 个分量，每个触点都构成了一个只含有它自己的分量，因此将 <code>id[i]</code> 初始化为 i，其中 i 为 0 到 N-1。<code>find()</code> 判定它所在分量所需的信息保存在 <code>id[i]</code> 之中。<code>connected()</code> 方法只有一条语句 <code>find(p)==find(q)</code>，它返回一个布尔值。</p>
</blockquote>
<h3 id="实现"><a href="#实现" class="headerlink" title="实现"></a>实现</h3><h4 id="1-quick-find-算法"><a href="#1-quick-find-算法" class="headerlink" title="1 quick-find 算法"></a>1 quick-find 算法</h4><h5 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">UF</span></span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] id;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> count;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">UF</span><span class="params">(<span class="keyword">int</span> N)</span></span>&#123;</div><div class="line">        id = <span class="keyword">new</span> <span class="keyword">int</span>[N];</div><div class="line">        count = N;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++)&#123;</div><div class="line">            id[i] = i;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">union</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> q)</span></span>&#123;</div><div class="line">        <span class="keyword">int</span> pid = find(p);</div><div class="line">        <span class="keyword">int</span> qid = find(q);</div><div class="line">        <span class="keyword">if</span>(pid == qid)&#123;</div><div class="line">            <span class="keyword">return</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; id.length; i++)&#123;</div><div class="line">            <span class="keyword">if</span>(id[i] == pid)&#123;</div><div class="line">                id[i] = qid;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        count--;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> p)</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> id[p];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">connected</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> q)</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> id[p] == id[q];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> count;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h5 id="分析"><a href="#分析" class="headerlink" title="分析"></a>分析</h5><p>上述代码的 find 方法十分高效，因为仅仅需要一次数组读取操作就能够找到该节点的组号，但是问题随之而来，对于需要添加新路径的情况，就涉及到对于组号的修改，因为并不能确定哪些节点的组号需要被修改，因此就必须对整个数组进行遍历，找到需要修改的节点，逐一修改，每次添加新路径带来的复杂度就是线性关系了，如果要添加的新路径的数量是M，节点数量是N，那么最后的时间复杂度就是MN，显然是一个平方阶的复杂度，对于大规模的数据而言，平方阶的算法是存在问题的，这种情况下，每次添加新路径就是“牵一发而动全身”，想要解决这个问题，关键就是要提高union方法的效率，让它不再需要遍历整个数组。</p>
<h4 id="2-quick-union-算法"><a href="#2-quick-union-算法" class="headerlink" title="2 quick-union 算法"></a>2 quick-union 算法</h4><h5 id="代码-1"><a href="#代码-1" class="headerlink" title="代码"></a>代码</h5><blockquote>
<p>id[] 数组用父链接的形式表示了一片森林，从任何触点所对应的节点开始跟随链接，最终都将到达含有该节点的树的根节点。quick-union 中 <code>union()</code> 的实现只用了一条语句就将一个根节点变为另一个根节点的父节点，从而归并了两棵树。</p>
</blockquote>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">QuickUnionUF</span></span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] id;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> count;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">QuickUnionUF</span><span class="params">(<span class="keyword">int</span> N)</span></span>&#123;</div><div class="line">        id = <span class="keyword">new</span> <span class="keyword">int</span>[N];</div><div class="line">        count = N;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++)&#123;</div><div class="line">            id[i] = i;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">union</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> q)</span></span>&#123;</div><div class="line">        <span class="keyword">int</span> pRoot = find(p);</div><div class="line">        <span class="keyword">int</span> qRoot = find(q);</div><div class="line">        <span class="keyword">if</span>(pRoot == qRoot)&#123;</div><div class="line">            <span class="keyword">return</span>;</div><div class="line">        &#125;</div><div class="line">        id[pRoot] = qRoot;</div><div class="line">        count--;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> p)</span></span>&#123;</div><div class="line">        <span class="keyword">while</span>(p != id[p])&#123;</div><div class="line">            p = id[p];</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> p;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">connected</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> q)</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> find(p) == find(q);</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> count;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h5 id="分析-1"><a href="#分析-1" class="headerlink" title="分析"></a>分析</h5><img src="/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/quick-union算法概述.png" title="quick-union算法概述">
<p>quick-union 算法看起来比 quick-find 算法更快，因为它不需要为每对输入遍历整个数组。但树这种数据结构容易出现极端情况，因为在建树的过程中，<strong>树的最终形态严重依赖于输入数据本身的性质</strong>，比如数据是否排序，是否随机分布等等。比如在<strong>输入数据是有序</strong>的情况下，构造的BST会退化成一个链表。如下图所示。</p>
<img src="/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/quick-union最坏情况.png" title="quick-union最坏情况">
<blockquote>
<p><strong>定义</strong>：一棵树的大小是它的节点的数量。树中一个节点的<strong>深度</strong>是它到根节点的路径上的<strong>链接（也就是边）数</strong>。<strong>树的高度</strong>是它的所有节点中的最大深度。<br><strong>命题</strong>：quick-union 算法中 find() 方法访问数组的次数为1加上给定触点所对应的节点的深度的两倍。union() 和 connected() 访问数组的次数为两次find() 操作（若union()中给定的两个触点分别存在于不同的树中则还需要加1）。</p>
</blockquote>
<p>由命题G可知，对于整数对0 i，union()操作访问数组的次数为<code>2i+2</code>（触点0的深度为i，触点i的深度为0）。因此，处理N对整数所需的所有find()操作访问数组的总次数为 $2(1+2+…+N)\sim N^2$。</p>
<h4 id="3-加权-quick-union-算法"><a href="#3-加权-quick-union-算法" class="headerlink" title="3 加权 quick-union 算法"></a>3 加权 quick-union 算法</h4><blockquote>
<p>只需简单修改quick-union算法就能保证像这样的最坏情况不会出现。与其在 union() 中随意将一棵树连接到另一棵树，现在记录每棵树的大小并总是将较小的树连接到大数上。此时需添加一个数组来记录树中节点数，将这种算法称为<strong>加权 quick-union 算法</strong>。该算法构造的树的高度也远远小于未加权版本构造的树的高度。</p>
</blockquote>
<h5 id="代码-2"><a href="#代码-2" class="headerlink" title="代码"></a>代码</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">WeightedUnionUF</span></span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] id;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> count;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span>[] sz;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">WeightedUnionUF</span><span class="params">(<span class="keyword">int</span> N)</span></span>&#123;</div><div class="line">        id = <span class="keyword">new</span> <span class="keyword">int</span>[N];</div><div class="line">        count = N;</div><div class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; N; i++)&#123;</div><div class="line">            id[i] = i;</div><div class="line">            sz[i] = <span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">union</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> q)</span></span>&#123;</div><div class="line">        <span class="keyword">int</span> pRoot = find(p);</div><div class="line">        <span class="keyword">int</span> qRoot = find(q);</div><div class="line">        <span class="keyword">if</span>(pRoot == qRoot)&#123;</div><div class="line">            <span class="keyword">return</span>;</div><div class="line">        &#125;</div><div class="line">        <span class="comment">//比较树大小，小树指向大树，修改大树大小</span></div><div class="line">        <span class="keyword">if</span>(sz[pRoot] &lt; sz[qRoot])&#123;</div><div class="line">            id[pRoot] = qRoot;</div><div class="line">            sz[qRoot] += sz[pRoot];</div><div class="line">        &#125;<span class="keyword">else</span>&#123;</div><div class="line">            id[qRoot] = pRoot;</div><div class="line">            sz[pRoot] += sz[qRoot];</div><div class="line">        &#125;</div><div class="line">        count--;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> p)</span></span>&#123;</div><div class="line">        <span class="keyword">while</span>(p != id[p])&#123;</div><div class="line">            p = id[p];</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">return</span> p;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">connected</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> q)</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> find(p) == find(q) ;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">count</span><span class="params">()</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> count;</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<h5 id="分析-2"><a href="#分析-2" class="headerlink" title="分析"></a>分析</h5><blockquote>
<p><strong>命题H</strong>：对于 N 个触点，加权 quick-union 算法够早的森林中的任意节点的深度最多为 lgN。<br><strong>推论</strong>：对于加权 quick-union 算法和 N 个触点，在最坏情况下 <code>find()、connected()</code> 和 <code>union()</code> 的成本增长数量级为 logN。</p>
</blockquote>
<p>命题H和推论的意义在于加权 quick-union 算法是三种算法中唯一可以用于解决大型实际问题的算法。加权 quick-union 算法处理N个触点和M条连接时最多访问数组 cMlgN 次，c为常数，比 quick-find（和某些情况下的quick-union）需要访问数组至少MN次形成鲜明对比。</p>
<img src="/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/各种union-find算法性能特点.png" title="各种union-find算法性能特点">
<h4 id="4-最优算法——基于quick-union-算法进行路径压缩"><a href="#4-最优算法——基于quick-union-算法进行路径压缩" class="headerlink" title="4 最优算法——基于quick-union 算法进行路径压缩"></a>4 最优算法——基于quick-union 算法进行路径压缩</h4><p>理想情况下，我们希望每个结点都直接链接到它的根节点，但又不想像quick-find那样通过修改大量链接实现，实际实现很简单——在检查节点时将它们直连到根节点。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> p)</span></span>&#123;</div><div class="line">    <span class="keyword">while</span>(p != id[p])&#123;</div><div class="line">        <span class="comment">//若当前节点非根节点</span></div><div class="line">        <span class="comment">//则使当前节点指向父节点的父节点/或直接指向根节点find(index)</span></div><div class="line">        id[p] = id[id[p]];</div><div class="line">        p = id[p];</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> p;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<blockquote>
<p>所得到的结果几乎是完全扁平化的树，即<strong>路径压缩的加权 quick-union 算法是最优的算法</strong></p>
</blockquote>
<h4 id="参考："><a href="#参考：" class="headerlink" title="参考："></a>参考：</h4><p><a href="http://blog.csdn.net/dm_vincent/article/details/7655764" target="_blank" rel="noopener">并查集(Union-Find)算法介绍</a></p>
<p><strong>前面两篇文章的相关代码地址：</strong><br><a href="https://github.com/fighterhit/algorithms/tree/master/src/main/java/algorithms/chapter1" target="_blank" rel="noopener">代码地址</a></p>

      
    </div>
    
    
    

    

    
      <div>
        <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
  <div>请我喝杯咖啡吧☕~</div>
  <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
    <span>打赏</span>
  </button>
  <div id="QR" style="display: none;">

    
      <div id="wechat" style="display: inline-block">
        <img id="wechat_qr" src="/images/wechatpay.jpg" alt="Fighter. 微信支付"/>
        <p>微信支付</p>
      </div>
    

    
      <div id="alipay" style="display: inline-block">
        <img id="alipay_qr" src="/images/alipay.jpg" alt="Fighter. 支付宝"/>
        <p>支付宝</p>
      </div>
    

    

  </div>
</div>

      </div>
    

    
      <div>
        <ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者：</strong>
    Fighter.
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/" title="（二）基础（Fundamentals）：算法分析">http://fighterhit.github.io/2017/12/30/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals-Time-Complexity/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>
    本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/" rel="external nofollow" target="_blank">CC BY-NC-SA 3.0</a> 许可协议。转载请注明出处！
  </li>
</ul>

      </div>
    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/算法/" rel="tag"># 算法</a>
          
            <a href="/tags/Algorithms-Notes/" rel="tag"># Algorithms Notes</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2017/12/27/algorithm_and_datastructure/Algorithms4/Ch1-Fundamentals/" rel="next" title="（一）基础（Fundamentals）：数据结构">
                <i class="fa fa-chevron-left"></i> （一）基础（Fundamentals）：数据结构
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2018/01/29/algorithm_and_datastructure/Algorithms4/Ch2-Sort/" rel="prev" title="（三）排序">
                （三）排序 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
        <!-- JiaThis Button BEGIN -->
<div class="jiathis_style">
<span class="jiathis_txt">分享到：</span>
<a class="jiathis_button_fav">收藏夹</a>
<a class="jiathis_button_tsina">新浪微博</a>
<a class="jiathis_button_qzone">QQ空间</a>
<a class="jiathis_button_weixin">微信</a>
<a class="jiathis_button_cqq">腾讯QQ</a>
<a class="jiathis_button_copy">复制网址</a>
<a class="jiathis_button_share">一键分享</a>

<a href="http://www.jiathis.com/share?uid=2140465" class="jiathis jiathis_txt jiathis_separator jtico jtico_jiathis" target="_blank">更多</a>
<a class="jiathis_counter_style"></a>
</div>
<script type="text/javascript" >
var jiathis_config={
  data_track_clickback:true,
  summary:"",
  shortUrl:false,
  hideMore:false
}
</script>
<script type="text/javascript" src="http://v3.jiathis.com/code/jia.js?uid=" charset="utf-8"></script>
<!-- JiaThis Button END -->
      
    </div>
  </div>


          </div>
          


          
  
    <div class="comments" id="comments">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zMjY0Ni85MjA3"></div>
    </div>
  


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/images/avatar.jpg"
                alt="Fighter." />
            
              <p class="site-author-name" itemprop="name">Fighter.</p>
              <p class="site-description motion-element" itemprop="description">学习 | 分享 | 交流 | 进步</p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">26</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">6</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">28</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          <div class="links-of-author motion-element">
            
              
                <span class="links-of-author-item">
                  <a href="https://github.com/fighterhit" target="_blank" title="GitHub">
                    
                      <i class="fa fa-fw fa-github"></i>GitHub</a>
                </span>
              
                <span class="links-of-author-item">
                  <a href="https://weibo.com/fighterhit" target="_blank" title="Weibo">
                    
                      <i class="fa fa-fw fa-weibo"></i>Weibo</a>
                </span>
              
            
          </div>

          
          

          
          

          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#观察"><span class="nav-number">1.</span> <span class="nav-text">观察</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#数学模型"><span class="nav-number">2.</span> <span class="nav-text">数学模型</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#近似"><span class="nav-number">2.1.</span> <span class="nav-text">近似</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#成本模型"><span class="nav-number">2.2.</span> <span class="nav-text">成本模型</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#构建运行时间的数学模型所需步骤："><span class="nav-number">2.3.</span> <span class="nav-text">构建运行时间的数学模型所需步骤：</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#设计更快的算法"><span class="nav-number">3.</span> <span class="nav-text">设计更快的算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#2-Sum-问题"><span class="nav-number">3.1.</span> <span class="nav-text">2-Sum 问题</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#3-Sum-问题"><span class="nav-number">3.2.</span> <span class="nav-text">3-Sum 问题</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#内存"><span class="nav-number">4.</span> <span class="nav-text">内存</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#对象"><span class="nav-number">4.1.</span> <span class="nav-text">对象</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#数组"><span class="nav-number">4.2.</span> <span class="nav-text">数组</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#字符串对象"><span class="nav-number">4.3.</span> <span class="nav-text">字符串对象</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#举例：union-find-算法"><span class="nav-number">5.</span> <span class="nav-text">举例：union-find 算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#动态连通性"><span class="nav-number">5.1.</span> <span class="nav-text">动态连通性</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#实现"><span class="nav-number">5.2.</span> <span class="nav-text">实现</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#1-quick-find-算法"><span class="nav-number">5.2.1.</span> <span class="nav-text">1 quick-find 算法</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#代码"><span class="nav-number">5.2.1.1.</span> <span class="nav-text">代码</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#分析"><span class="nav-number">5.2.1.2.</span> <span class="nav-text">分析</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#2-quick-union-算法"><span class="nav-number">5.2.2.</span> <span class="nav-text">2 quick-union 算法</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#代码-1"><span class="nav-number">5.2.2.1.</span> <span class="nav-text">代码</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#分析-1"><span class="nav-number">5.2.2.2.</span> <span class="nav-text">分析</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#3-加权-quick-union-算法"><span class="nav-number">5.2.3.</span> <span class="nav-text">3 加权 quick-union 算法</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#代码-2"><span class="nav-number">5.2.3.1.</span> <span class="nav-text">代码</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#分析-2"><span class="nav-number">5.2.3.2.</span> <span class="nav-text">分析</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#4-最优算法——基于quick-union-算法进行路径压缩"><span class="nav-number">5.2.4.</span> <span class="nav-text">4 最优算法——基于quick-union 算法进行路径压缩</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#参考："><span class="nav-number">5.2.5.</span> <span class="nav-text">参考：</span></a></li></ol></li></ol></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      
      
    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2016 - <span itemprop="copyrightYear">2018</span>
  <span class="with-love">
    <i class="fa fa-home"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Fighter.</span>

  
</div>









        
<div class="busuanzi-count">
  <!--<script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>-->
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="site-uv">
      <i class="fa fa-user"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
      
    </span>
  

  
    <span class="site-pv">
      <i class="fa fa-eye"></i>
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
      
    </span>
  

    <span class="site-pv">&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;
    Hosted by <a target="_blank" href="https://github.com/">GitHub Pages</a>
    </span>

</div>







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.3"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.3"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.1.3"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.1.3"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.3"></script>



  


  




	





  





  
    <script type="text/javascript">
      (function(d, s) {
        var j, e = d.getElementsByTagName(s)[0];
        if (typeof LivereTower === 'function') { return; }
        j = d.createElement(s);
        j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
        j.async = true;
        e.parentNode.insertBefore(j, e);
      })(document, 'script');
    </script>
  








  





  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script><!-- hexo-inject:begin --><!-- hexo-inject:end -->
  


  

  

</body>
</html>
